package com.smh;

/**
 * @author shiminghui
 * @date 2025/2/7 11:15
 * @description: TODO
 */
public class _010_链表 {

    // 根据值删除元素
    public ListNode removeElements(ListNode head, int val) {
        while (head != null && head.val == val) {
            head = head.next;
        }
        if (head == null || head.next == null) { // 元素删除完了，或者只有一个元素
            return head;
        }

        ListNode pre = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return head;
    }

    // 使用哨兵
    public ListNode removeElements2(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    // 使用递归实现
    public ListNode removeElements3(ListNode head, int val) {
        if (head == null) {
            return null;
        }

        ListNode listNode = removeElements3(head.next, val);
        head.next = listNode; // 递归返回的时候，如果当前节点的值等于val，那么就返回当前节点的下一个节点，否则返回当前节点

        if (head.val == val) {
            return listNode;
        } else {
            return head;
        }
    }


    // 删除链表中倒数第n个节点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int[] index = new int[1];
        ListNode digui = digui(head, n, index);
        return digui;
    }

    private ListNode digui(ListNode head, int n, int[] index) {
        if (head == null) {
            index[0] = 0;
            return null;
        }
        ListNode listNode = digui(head.next, n, index);
        head.next = listNode;
        index[0]++;
        if (index[0] == n) {
            return listNode;
        } else {
            return head;
        }
    }

    // 优化递归,不过得加个哨兵
    private int digui2(ListNode head, int n) {
        if (head == null) {
            return 1;
        }
        int index = digui2(head.next, n);
        if (index == n + 1) {
            head.next = head.next.next;
        }
        return (index + 1);
    }

    //不用递归，而是用两个指针
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        ListNode cur = dummy;
        int flag = 0;
        while (cur != null) {
            if (flag > n) {
                pre = pre.next;
            }
            cur = cur.next; // 循环结束的时候，cur指向最后一个节点，pre指向倒数第n+1个节点
            flag++;
        }
        pre.next = pre.next.next;
        return head;
    }

    // 83. 删除排序链表中的重复元素
    // 双指针
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode o1 = head;
        ListNode o2 = head.next;
        while (o2 != null) {
            if (o1.val == o2.val) {
                o1.next = o2.next;
                o2 = o2.next;
            } else {
                o1 = o1.next;
                o2 = o2.next;
            }
        }
        return head;
    }

    //递归实现
    public ListNode deleteDuplicates2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode listNode = deleteDuplicates2(head.next);
        if (head.val == listNode.val) {
            head.next = listNode.next;
        }
        return head;
    }

    // 82. 删除排序链表中的重复元素 II（全部删除）
    public ListNode deleteDuplicates3(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1, head); // 哨兵
        ListNode pre = dummy;
        ListNode cur = head;
        ListNode next = head.next;
        while (next != null) {
            if (cur.val == next.val) {
                while (next != null && cur.val == next.val) {
                    next = next.next;
                }
                pre.next = next;
                cur = next;
                next = next == null ? null : next.next;
            } else {
                pre = cur;
                cur = cur.next;
                next = next.next;
            }
        }
        return dummy.next;
    }

    // 使用递归
    public ListNode deleteDuplicates4(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
        ListNode digui = digui(dummy, new int[1]);
        return digui.next;
    }

    // 这是在归的时候才判断的
    public ListNode digui(ListNode head, int val[]) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode listNode = digui(head.next, val);
        head.next = listNode;
        if (head.val == listNode.val) {
            val[0] = 1;
            return listNode;
        } else {
            if (val[0] != 0) {
                head.next = listNode.next;
            }
            val[0] = 0;
            return head;
        }

    }

    // 在递的时候判断的
    public ListNode digui2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            // 找到重复节点的下一个
            while (head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            return digui2(head.next);
        } else {
            // 不同时，返回当前节点
            ListNode listNode = digui2(head.next);
            head.next = listNode;
            return head;
        }
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
